The present invention relates to a versatile ATM cell switch element ASIC having provisions for expandability of number of buffers used to store the cells, and for efficient implementation of internal queues by utilizing the slicing concept. Further the ATM ASIC of the present invention possesses an advantage of configurability of the speeds of input streams while maintaining the total throughput.
The ACE ASIC of the present invention is capable of operating at a standard basic link speed, multiples of standard basic link speed and/or combinations thereof while maintaining a constant throughput, without requiring change in the architecture of the switching element. The expandability of the number of buffers, i.e., buffer expansion, used to store the cells is enabled by equipping more devices.
The broadband integrated services digital network (BISDN) which provides for high speed and high density data communications while integrating voice, video and data over a single speed network, are being commercially exploited. CCITT standards recommend implementation of asynchronous transfer mode (ATM) packet switching in BISDN applications which utilizes packet switches for routing information in fixed size data packets called cells between a plurality of inputs and outputs.
Prior art ATM packet switches generally include single stage switches e.g., knock out switch and multistage switches, e.g., starlight switch, each being manifest with their own problems. The knock out switch architecture suffers from several limitations that limit its use in broadband applications. It requires a large number of packet filters and large concentrator which significantly increases the cost and complexity of the packet switches, especially for networks with a great number of inputs and outputs. Another limitation of the knock out switch architecture is that it utilizes a large number of memory buffers for output buffering and requires memory speed-up to accept multiple packets simultaneously at each output port. Additionally knock out type switches do not include the means for sorting data packets for priority and therefore require additional hardware for this function. Finally the implementation of multicasting in a knock out switch requires each output port to first accept all multicast packets and then to reject those that do not belong to it. This also requires additional hardware including large memory buffers to store all the multicast addresses and additional logic to determine whether to accept or reject a multicast packets at the output port.
Similarly starlight switch also suffers from several limitations that limit its utility in broadband applications. For example, to achieve low packet loss, the starlight architecture requires a large sorter and trap network, thereby increasing the number of sorting and switching elements several fold. Additionally the starlight architecture is not modular or expandable in small increments and requires a separate copy network thus increasing the cost of the switch.
Another type of the prior art packet switch is shared buffer switch which finds limited use because it must be operated at a much higher speed for writing all the packets in one clock cycle, thus often introducing head of line blocking. Additionally these switches do not offer a priority mechanism and are not modular.
U.S. Pat. No. 6,011,779 relates to a switch queuing system for transferring cells from a plurality of input channels to a plurality of output channels where the switching system claims to minimize the cell loss for bursty traffic while delay for time-critical data is also avoided. The ATM switch drops cell on a per connection basis, rather than on cell priority level. The sender(s) of the congestion causing data is penalized, rather then other users of the ATM switch.
U.S. Pat. No. 6,009,078 relates to an ATM switch capable of favorably controlling traffic congestion. The ATM switch structure is capable of detecting the traffic congestion all over the ATM switch device by the total queue monitoring buffer and to assure delivery of the output cells equal to the minimum guaranteed value. Each minimum guaranteed value may be determined for each service class and a multicast cell.
U.S. Pat. No. 5,875,190, relates to an ATM switching system, for distributing and concentrating input data packets that is comprised of a distribution section and a concentration section comprising N-priority concentration sorters each having N inputs and L outputs, L being less than N. The sorters comprise means for ordering data packets according to priority information and for transferring only the L data packets according to priority information and for transferring only the L data packets from N inputs which have the highest relative priorities. A multiplicity of the switching arrangements can be interconnected to provide an expanded switching arrangement.
U.S. Pat. No. 5,271,004 relate to an asynchronous transfer mode switching arrangement providing broadcast transmission which includes a serial to parallel converter arranged to receive input packets of data which include routing information, in serial form and convert the packets of data to parallel form. A first random access memory is provided in which each packet of data is entered at an addressed location into the memory, and the address is entered in a respective first-in first-out output queue at the tail.
U.S. Pat. No. 5,859,846 defines a fully interconnected ATM switching apparatus comprising a plurality of line interface circuits, each of the line interface circuits including an input port driver for extracting an SDH transmission frame containing cell data with a fixed length and a connection identifier from an input signal, appending a routing tag to the extracted SDH transmission frame through an input dedicated bus and an output port driver for receiving a cell stream from an output dedicated bus, removing the routing tag from the received cell stream, translating a channel identifier in the connection identifier and transferring the resultant SDH transmission frame to an adjacent node, a system clock distributor for generating a clock signal, an initialization controller for controlling a system and restart operations, a switch maintenance controller for performing a switch maintenance control operation in response to a network managing cell, a switch call processing controller for performing a call processing operation, a switch module controller for controlling a switching operation, and a plurality of switch output multiplexers for switching cells from the input port drivers to the output port drivers under the control of the switch module controller.
U.S. Pat. No. 6,009,100 relates to an asynchronous transfer mode switching network can be made to look like a synchronous tandem switch to end offices connected to the network by establishing a permanent virtual path through the network that carries information between the end offices. Individual channels to be switched are assigned ATM VCI addresses at both ends that correspond to the time slot to the time slot channel being sent and a time slot channel being received.
U.S. Pat. 5,636,210 claims to employ an inexpensive and efficient architecture that is modular and expandable. This patent incorporates priority sorting and improved multicasting while requiring a minimum amount of memory buffers. This patent discloses an ATM packet switch for routing data packets between a plurality of input and output devices. It claims to provide a high degree of modularity by allowing expansion of the switch to handle applications having less than eight input and output devices to applications having 214 input and output devices. This patent broadly classifies the single stage switch, two stage switch and three stage asynchronous packet switches each being capable of routing packets between different number of input and out devices. The single stage packet switching is used for routing data packets between eight or less input and output devices by using a single output group modules and is expanded for routing data packets between up to 26 input and output devices by coupling as many as four output group modules together. The two stage asynchronous transfer mode packet switch is most efficient for routing data packets between up to 210 input and output devices and includes a plurality of input group modules, a broadcast and recirculation module and a plurality of output group modules. Similarly three stage asynchronous transfer mode packet switch as disclosed provides an additional switching stage for applications with more than 210 input and output devices. The preferred three stage asynchronous transfer mode packet switch broadly includes a plurality of input planes and a plurality of output planes.
However, architecture for the above switch as claimed in the above patent does not provide any configurability. If designed to operate at a standards basic link speed the switch can not operate at higher speeds, e.g. an architecture designed for STM -1 works only for STM-1 and can not work for STM-4 link speed. The configurability of link speeds is a required characteristic as this obviates the need for designing different switches for different link speeds.
Further the single stage switches and the multi staged switches employs use of banyan router consuming a large amount of space. This technology is therefore not preferred as per the presently available ASIC technology. The space constraint leads to a heavier hardware configuration.
However, it is still desired to provide an ATM switch having provisions for buffer expansion, efficient handling of internal queuing and configurability of the switch to receive input at various speeds.
The present invention relates to an ATM cell switch element, ACE ASIC, which is an implementation of an ATM self-routing fabric using shared buffer, output queuing technique. The gross functionality of the ASIC is to automatically route incoming packets of data (referred to as cells) to their destinations. The switching is done based on a xe2x80x9crouting tagxe2x80x9d that is prepended to the packet. This routing tag informs the switch about the destination(s) of the packet and the priority of the packet. The priority information is used to xe2x80x9csortxe2x80x9d the packets internal to the switch so that the packets with higher priority are delivered before others.
Due to statistical distribution of the incoming traffic of the packets, there is a necessity of storing the packets inside the switch in a queue. During a given packet time, there may be more than one packet that is destined to an output port. In this case, the priority of the packet is used to determine which of them would be delivered first to the output port. The other packets are stored in the switch inside a queue for delivery at a later time.
Based on this functionality, the sub-tasks that the switch has to perform include the task of receiving the input packet and detaching the routing tag from the packet. Thereafter the routing tag is understood/interpreted and the destination port(s) is/are identified. An internal storage location is thereafter identified for receiving this packet. After this location is determined, the packet is to be written into this location.
After all the incoming packets of a cell time have been received, the desired destinations have to be scanned in order to determine the packets that have to be read out on each output. After the packets with the highest priority have been selected, these have to be read from the internal storage location and delivered to the respective ports.
The corresponding sub-modules that perform these tasks are
1. Routing Tag Detachment (RTD) that receives the cell and separates the routing tag from the cell.
2. Buffer Assignment Module (BAM) that understands the routing tag and determines the desired destination port(s), searches and allocates an internal storage buffer to hold this incoming packet.
3. Input Crossbar Switch (ICS) that routes the incoming packet to the buffer allocated and facilitates the writing of the packet into this buffer.
4. Shared Cell Buffer Pool (SBP) that houses the storage buffers of the switch.
5. Queue Management Module (QMM) that receives the allocated buffer addresses from the BAM and the corresponding destination port(s) and xe2x80x9csequencesxe2x80x9d the reading of the buffers from the SBP based on the priority of the packets.
6. Output Crossbar Switch (OCS) that routes the packet read out from the SBP towards the destination output port.
The ACE ASIC of the present invention is an improvement over prior art as the switch of the present invention supports additional features as well that makes it a versatile ACE ASIC. The additional features in the ACE ASIC are
1. The expandability of the number of buffers used to store the cells by equipping more devices.
2. The configurability of the speeds of input streams among a standard basic link speed, multiples of standard basic link speed and/or any combination of the above while maintaining the total throughput.
3. The efficient implementation of internal queues by utilizing the xe2x80x9cslicexe2x80x9d concept.
Apart from the addition of these three features, another improvement incorporated in the ACE ASIC of the present invention is that the internal structure of the ICS and the OCS modules have been changed from a Banyan implementation to a crossbar implementation in order to save the area occupied by these modules within the ASIC. Banyan router has not been used thereby saving a lot of space. By merging regular buffer and overflow buffers the ASIC of the present invention has been made more implementable.
The dimensioning of the number of internal buffers supported within a switch fabric determine, to a large extent, the traffic handling capacity of the switch fabric. The buffer requirements therefore vary depending upon the traffic that a switch is designed to support. Accordingly, either the switch should be designed to support the highest number of buffers that would be required or should have some means to add buffers as necessary. The cost of providing the maximum size buffers inside an ASIC is quite high. The normal expansion method of adding more memory outside the ASIC is not a good enough solution as it generally places very high requirements on the external memory device and consumes additional pins on the device.
In the method of expansion used in the ATM switch of the, present invention, both the problems stated above are taken care of. First, the switch is designed with a certain number of buffers that suffices to serve moderate traffic requirements. Further, more buffer capacity is added by using, not an external memory, but the same switch in xe2x80x9cparallelxe2x80x9d with the first one. Thus, all that is required is to inform the two devices about the total equipage and the capacity is enhanced accordingly.
In an another embodiment of the present invention, the switch is designed to support input data from a multitude of network elements. These inputs may be coming from links operating at different speeds. A configurable switch matrix is needed for easy use in designs. This does not need the switch to actually work at many different physical speeds. Though such an implementation is possible, it is very complex to realize one. The present invention overcomes the drawbacks of the prior art by using some external multiplexing and de-multiplexing, configured at single constant clock. The ATM switch of the instant invention provides configurability of input speeds among standards basic link speeds, multiples of standards basic link speeds and/or combination of the above, while maintaining the total throughput. The external function for this involves slowing down the physical rate of the faster input links to the speed of the slowest link speed supported by distributing the data onto multiple lines. A speed reduction of xc2xc for instance, is obtained by redistributing the input data onto four physical lines. The physical speed of these four lines is then xc2xcth the original speed, while the information rate is the same if all the lines are considered together. Since the basic switch fabric assumes the presence, of complete cells on all its inputs a cell-wise de-multiplex functionality is implemented.
This splitting alone does not complete the support for multiple speed links. The order of delivery is also guaranteed by the switch matrix, i.e., the cells that are delivered are in the same order as they were received in.
In order to support this, the switch fabric maintains a single internal queue for all the xe2x80x9csub-linksxe2x80x9d of a logical link, though they go out on different physical lines. For example, if there is a 1-4 increase in the link speed, all th data that goes out of the device at a particular (logical) port, are queued up into a single physical queue. During the read-out from the device, this single queue is read four times, but onto four different lines to achieve a 1-4 speed advantage. These four lines are then multiplexed external to the switch to get the high-speed link. The ACE ASIC of the present invention provides for such demultiplexing and multiplexing by use of cell demultiplexer and cell multiplexer.
Further, a common practice in ASIC implementations of switch fabrics is to use a serial-to-parallel converter at the input of the devices in order to slow down the physical speed of operation. Normally, in the case of ATM cell switches, the input links are converted into a 4-bit wide bus so that the operating speed is reduced to a fourth of the line rate. These four input lines are handled either in the same switch or by four separate switches. In the first implementation, called the parallel mode, the number of physical inputs/outputs gets limited as each link now uses four pins of the switch. In the ATM cell switch element, since the design supports a relatively high number of inputs, the second mode, called the sliced mode is used. In this mode, each switch operates only on one of the 4-bit parallel bus. Four switches operate in tandem to realize the complete switch fabric.
In the ACE design of the present invention, an advantage is taken of the fact that for a complete switch fabric, more than one switches (N devices; where N is preferably 4) are present on the board. The QMM uses internal storage structures to organize the queues. The length of the queues supported in a switch is a parameter that determines its traffic handling capacity. More the length of queue that is supported, the better the traffic handling capacity. Here, again, there is the restriction that the increase in the internal memory requirement would lead to additional cost. The ACE of the instant invention is such that each switch holds memory to support only 1/N of the total queue length. By utilizing the fact that there would be Nxe2x88x921 other devices on the board, the memory is distributed across them leading to less area requirement inside one single switch.
Thus the present invention provides a versatile ATM switch which incorporates the features of configurability of speeds, slicing of internal queues to enable efficient implementation and also allows expandability of buffers required to store the cells by equipping more devices.
Apart from these basic functionality, the switch fabric also does some auxiliary functions which include counting the total number of cells that are currently stored inside the switch, the number of cells that are in the queue for each of the ports and the like. The switch here is told to look for certain xe2x80x9ceventsxe2x80x9d in the switch like the buffer occupancy levels crossing predetermined thresholds, the queue lengths crossing thresholds etc. Upon occurrence of any of these events, the switch is then asked to inform the external control circuitry by means of an xe2x80x9cinterruptxe2x80x9d. For all these, and other control functions that need to be exercised, there is a separate interface designated as the Processor Interface managed by a Processor Interface Module (PIM) provided in the ATM switch of the present invention.
The present invention uses RAM based buffer assignment modules and queue assignment modules while U.S. Pat. No. 5,636,210 has specified use of registers in buffer management module and in read sequencer module This involves less power dissipation and less logic thus becoming an implementable VLSI. Further, in U.S. Pat. No. 5,636,210 the IBSM was banyan router which again is a register base technology which requires change in operating frequency within the switch as the same uses higher operating frequency for the entire switch. Since it is a register based technology and since the operating frequency is higher, power dissipation is also higher. The banyan router also requires larger area. This has now been efficiently replaced by a crossbar switch obviating the problems related to frequency and power dissipation. The organization of buffers in this U.S. Pat. No. 5,636,210 was such that there were 2 sets of buffers called regular buffers and set of overflow buffers. This concept was changed with only one set of normal buffers. The present invention further provides efficient implementation of internal queue while also allowing configurability of speeds.
The present invention relates to an ATM switch having a plurality of input ports and a plurality of output ports allowing a plurality of priority levels, which is highly modular, allowing expansion of the number of cell buffers in a shared buffer pool, thus efficiently handling bursty traffic of one to one and one to many destination ports, using the bit slicing concept to reduce the operating speed of the switch and decrease the cell buffer size requirement per slice along with reducing the number of shared queue memories per slice, aiding cost effective and efficient, very large scale integration (VLSI) implementation. It also allows configurability of input link speeds while taking care of the order of cell delivery to the out put ports.
In a specific embodiment of the present invention the switch of the present invention exhibits modularity, for example, a 64xc3x9716 switch is capable of being configured to 64xc3x9764 switch by adding devices in parallel to work as a single stage switch.
In an another embodiment of the present invention the switch of the present invention is capable of reducing the operating speed of the switch while decreasing the cell buffer size requirement along with reducing the number of shared queue memories, aiding cost effective and efficient VLSI implementation. A bit slicing concept is used where the cell buffer size requirement per slice is reduced as well as the number of shared queue memories per slice is also reduced.
In a further embodiment of the present invention, the switch. of the instant invention allows configurability of input link speeds while taking care of the order of cell delivery to the output ports.
Accordingly the present invention relates to an ATM switch for switching cells from a plurality of input ports to a plurality of output ports supporting a plurality of priority levels, comprising
a routing tag detachment module for filtering the input cells, extracting the routing tag from the said filtered input cells, delaying the said filtered cells till the routing tag is processed;
a buffer assignment module for decoding the said routing tag received from the said routing tag detachment module, generating a cell destination port map and priority levels, allocating an internal cell buffer for the incoming cells, deallocating the corresponding cell buffer for outgoing cell, one or more configuration ports provided in the said buffer assignment module for configuring the total number of buffers available;
an input cross bar switch for transmitting cells from the said routing tag detachment module to the said cell buffers allocated by the said buffer assignment module, generating the required control signals for writing the transmitted cell to the said allocated cell buffer, said cell buffer being housed in a shared cell buffer pool organized as a bank of a plurality of groups each containing a plurality of cell buffers;
a queue management module having shared queue memories for receiving the allocated buffer addresses, corresponding cell destination port maps and the priority level of the cells from the said buffer assignment module, sequencing the reading of said cell buffers from the said shared cell buffer pool based on the priority level of the cells; and
an output cross bar switch for transmitting the cells read out from the said shared cell buffer pool to the said output ports of the said switch.
Further, in an another embodiment the present invention relates to an ATM switch for switching cells from a plurality of input ports to a plurality of output ports supporting a plurality of priority levels, comprising a N-bit demultiplexer at the input port for slicing the incoming cells into N bit slices thus reducing the speed of operation by a factor of N and reducing the depth of the shared buffer pool storing the cells by a factor of N, each bit slice being delivered to a routing tag detachment module of the said ATM switch for filtering the sliced input cells, extracting the routing tag from the said filtered input cells, delaying the said filtered cells till the routing tag is processed;
a configurable buffer assignment module for decoding the said routing tag received from the said routing tag detachment module generating a cell destination port map and priority levels, allocating an internal cell buffer for the incoming cells, deallocating the corresponding cell buffer for outgoing cell, one or more configuration ports provided in the said buffer assignment module for configuring the total number of buffers available;
an input cross bar switch for transmitting cells from the said routing tag detachment module to the said cell buffers allocated by the said buffer assignment module, generating the required control signals for writing the transmitted cell to the said allocated cell buffer, said cell buffer being housed in a shared cell buffer pool organized as a bank of plurality of groups each containing a plurality of cell buffers, one or more configuration ports provided in the said input crossbar switch for determining the specific range of cell buffer addresses supported by the said shared cell buffer pool;
a queue management module having shared queue memories placed across all the xe2x80x98Nxe2x80x99 slices thus reducing the queue memories in each slice by a factor of N thereby reducing the area of queue management module, for receiving the allocated buffer addresses, corresponding cell destination port maps and the priority level of the cells from the said buffer assignment module, sequencing the reading of said cell buffers from the said shared cell buffer pool based on the priority level of the cells, one or more configuration ports provided in the said queue management module for configuring the said bit slice numbers, determining the specific range of queue memory addresses supported by each of the said queue management modules;
an output cross bar switch comprising one or more configuration ports determining the specific range of cell buffer addresses supported by the said shared cell buffer pool, for transmitting the cells read out from the said shared cell buffer pool to an N-bit multiplexer for recombining the N-bit sliced outputs from the N-output crossbar switches at the output port of the said switch.
Further, the present invention also relates to an ATM switch for switching cells from a plurality of input ports to a plurality of output ports supporting a plurality of priority levels, accepting inputs at a standard basic link speed, multiples of the standard basic link speed and combinations thereof while maintaining a constant throughput by the use of a cell demultiplexer at the input port for inputs operating at speeds higher than the standard basic link speed, comprising a N-bit demultiplexer at the input port for slicing the incoming cells into N bit slices thus reducing the speed of operation by a factor of N and reducing the depth of the shared buffer pool storing the cells by a factor of N, each bit slice being delivered to a routing tag detachment module of the said ATM switch for filtering the input cells, extracting the routing tag from the said filtered input cells, delaying the said filtered cells till the routing tag is processed;
a configurable buffer assignment module for decoding the said routing tag received from the said routing tag detachment module generating a cell destination port map and priority levels, allocating an internal cell buffer for the incoming cells, deallocating the corresponding cell buffer for outgoing cell, one or more configuration ports provided in the said buffer assignment module for configuring the total number of buffers available;
an input cross bar switch for transmitting cells from the said routing tag detachment module to the said cell buffers allocated by the said buffer assignment module, generating the required control signals for writing the transmitted cell to the said allocated cell buffer, said cell buffer being housed in a shared cell buffer pool organized as a bank of plurality of groups each containing a plurality of cell buffers, one or more configuration ports provided in the said input crossbar switch for determining the specific range of cell buffer addresses supported by the said shared cell buffer pool;
a queue management module having shared queue memories placed across all the xe2x80x98Nxe2x80x99 slices thus reducing the queue memories in each slice by a factor of N thereby reducing the area of queue management module, for receiving the allocated buffer addresses, corresponding cell destination port maps and the. priority level of the cells from the said buffer assignment module, sequencing the reading of said cell buffers from the said shared cell buffer pool based on the priority level of the cells, one or more configuration ports provided in the said queue management module for configuring the said bit slice numbers, determining the specific range of queue memory addresses supported by each of the said queue management modules, maintaining a single queue across multiple output ports for links operating at speeds higher than the standard basic link speed to ensure the order of delivery of cell in conformity with the order of the cell arrival at the input for all cells within each ATM connection;
an output cross bar switch comprising one or more configuration ports determining the specific range of cell buffer addresses supported by the said shared cell buffer pool, for transmitting the cells read out from the said shared cell buffer pool to an N-bit multiplexer for recombining the N-bit sliced outputs from the N-output crossbar switches; and
a cell multiplexer receiving the said recombined cells at output ports operating at speeds higher than the standard basic link speed to obtain the cells at the desired operating speeds.